﻿class Solution
{
public:
	int solve(vector<vector<char>>& grid)
	{
		int ret = 0; // 记录最终结果 
		int m = grid.size(), n = grid[0].size();
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (grid[i][j] == '1')
				{
					ret++; // 发现⼀个岛屿 
					dfs(grid, i, j); // 把这个岛屿全部修改成 '0' 
				}
			}
		}
		return ret;
	}
	int dx[4] = { 0, 1, -1, 0 };
	int dy[4] = { 1, 0, 0, -1 };
	void dfs(vector<vector<char>>& grid, int i, int j)
	{
		grid[i][j] = '0'; // 把该位置先变成 '0' 
		int m = grid.size(), n = grid[0].size();
		// 遍历相邻的所有位置 
		for (int k = 0; k < 4; k++)
		{
			int x = i + dx[k], y = j + dy[k];
			if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1')
				dfs(grid, x, y);
		}
	}
};